#include <stdio.h>
#include <stdlib.h>

#define Max 10
// 定义多项式的节点结构
typedef struct PolyNode
{
    int coefficient;       // 系数
    int exponent;          // 指数
    struct PolyNode *next; // 下一个节点指针
} PolyNode;

// 创建一个多项式节点
PolyNode *createNode(int coef, int exp)
{
    PolyNode *newNode = (PolyNode *)malloc(sizeof(PolyNode));
    newNode->coefficient = coef;
    newNode->exponent = exp;
    newNode->next = NULL;
    return newNode;
}

// 将新节点插入多项式链表
void insertNode(PolyNode *head, int coef, int exp)
{
    PolyNode *newNode = createNode(coef, exp);
    PolyNode *current = head;

    while (current->next != NULL)
    {
        current = current->next;
    }

    current->next = newNode;
}

// 打印输出多项式
void printPoly(PolyNode *head)
{
    PolyNode *current = head->next;
    while (current != NULL)
    {
        printf("%dx^%d ", current->coefficient, current->exponent);
        current = current->next;
        if (current != NULL)
        {
            printf("+ ");
        }
    }
    printf("\n");
}

// 多项式相乘
PolyNode *multiplyPoly(PolyNode *poly1, PolyNode *poly2)
{
    PolyNode *result = createNode(0, 0); // 结果多项式的头节点

    // 对第一个多项式的每一项进行遍历
    PolyNode *current1 = poly1->next;
    while (current1 != NULL)
    {
        // 对第二个多项式的每一项进行遍历
        PolyNode *current2 = poly2->next;
        while (current2 != NULL)
        {
            int coef = current1->coefficient * current2->coefficient; // 系数相乘
            int exp = current1->exponent + current2->exponent;        // 指数相加

            // 在结果多项式中查找是否有相同指数的项
            PolyNode *currentResult = result;
            while (currentResult->next != NULL && currentResult->next->exponent > exp)
            {
                currentResult = currentResult->next;
            }

            if (currentResult->next != NULL && currentResult->next->exponent == exp)
            {
                // 如果有相同指数的项，则系数相加
                currentResult->next->coefficient += coef;
            }
            else
            {
                // 如果没有相同指数的项，则插入新节点
                insertNode(currentResult, coef, exp);
            }

            current2 = current2->next;
        }
        current1 = current1->next;
    }

    return result;
}

void input(int num[], int zet[], int &count)
{
    printf("请依次输入一元多项式的指数(不超过10个,以-1结束)：\n");
    scanf("%d", &num[count]);
    while (num[count] != -1)
    {
        count++;
        scanf("%d", &num[count]);
    }
    printf("请依次输入对应指数的系数：\n");
    for (int i = 0; i < count; i++)
        scanf("%d", &zet[i]);
}

int main()
{
    // 创建第一个多项式
    int coef1[Max], exp1[Max], count1 = 0;
    input(exp1, coef1, count1);
    PolyNode *poly1 = createNode(0, 0);
    for (int i = 0; i < count1; i++)
    {
        insertNode(poly1, coef1[i], exp1[i]);
    }
    printf("多项式1: ");
    printPoly(poly1);

    // 创建第二个多项式
    int coef2[Max], exp2[Max], count2 = 0;
    input(exp2, coef2, count2);
    PolyNode *poly2 = createNode(0, 0);
    for (int i = 0; i < count2; i++)
    {
        insertNode(poly2, coef2[i], exp2[i]);
    }
    printf("多项式2: ");
    printPoly(poly2);

    // 计算相乘结果多项式
    PolyNode *result = multiplyPoly(poly1, poly2);
    printf("相乘结果: ");
    printPoly(result);

    return 0;
}
//第一个多项式的指数：2 1 0 -1
//第一个多项式的系数： 2 3 4
//第二个多项式的指数： 1 0 -1
//第二个多项式的系数： 1 1
//结果：2x^3 + 5x^2 + 7x^1 + 4x^0